package com.ryujung.dfs_backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution131 {
    /**
     * 方式二：动态规划 + 回溯
     * <p>
     * dp[i][j] 为s中substring(i,j+1)是否为回文的判断数组
     * 回溯过程中直接判断dp[i][j]来确定当前的值是否为回文
     */
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        // 先遍历右边界，关键步骤！！！
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                // 不能直接通过另一个函数判断，这样就失去了动态规划的意义，造成性能浪费
//                dp[i][j] = isPalindrome(s, i, j);

                // 只需对结果为true的值进行赋值操作，其他默认为false
                // 注意： ||（或）条件中的先后顺序，如果颠倒会报错！
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        Deque<String> stk = new ArrayDeque<>();
        dfsAndDp(s, 0, dp, stk, res);
        return res;
    }

    private void dfsAndDp(String s, int index, boolean[][] dp, Deque<String> stk, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(stk));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (dp[index][i]) {
                stk.addLast(s.substring(index, i + 1));
                dfsAndDp(s, i + 1, dp, stk, res);
                stk.removeLast();
            }
        }
    }

    /**
     * 方式一：回溯算法
     * <p>
     * 思路：
     * 已知的条件
     * 要保证s中的每个字符都在结果集中
     * 结果集中的所有字符串都是回文串
     * 所有的组合都要列出
     * <p>
     * 使用回溯算法来组合出所有的字符组合
     * 当s中所有字符使用完，则结束，并加入结果集
     */
    public List<List<String>> partition1(String s) {
        List<List<String>> res = new ArrayList<>();
        Deque<String> stk = new ArrayDeque<>();
        dfs(s, 0, stk, res);
        return res;
    }

    // 优化第一次通过的题解
    // 解答成功:
    //	执行耗时:8 ms,击败了54.63% 的Java用户
    //	内存消耗:53.8 MB,击败了54.04% 的Java用户

    /**
     * 官方解释：
     * 时间复杂度:O(n*2^n)，其中 n 是字符串 s 的长度。
     * 在最坏情况下，s 包含 n 个完全相同的字符，
     * 因此它的任意一种划分方法都满足要求。
     * 而长度为 n 的字符串的划分方案数为2^(n−1)=O(2^n)，
     * 每一种划分方法需要 O(n) 的时间求出对应的划分结果并放入答案，
     * 因此总时间复杂度为 O(n*2^n)。
     * 尽管动态规划预处理需要 O(n^2) 的时间，
     * 但在渐进意义下小于 O(n*2^n)，因此可以忽略。
     * <p>
     * 空间复杂度：O(n^2)，这里不计算返回答案占用的空间。
     * 数组 f 需要使用的空间为 O(n^2)，而在回溯的过程中，
     * 我们需要使用 O(n) 的栈空间以及 O(n) 的用来存储当前字符串分割方法的空间。
     * 由于 O(n) 在渐进意义下小于 O(n^2)，因此空间复杂度为 O(n^2)。
     * <p>
     * <p>
     * 个人理解的时间复杂度：
     * 每一个位置可拆分，也可不拆分，尝试是否可以拆分的时间复杂度为2^(n-1)= O(2^n)，
     * 判断每一个子串是否是回文子串，时间复杂度为 O(n)；即O(n*2^n)
     */
    private void dfs(String s, int index,
                     Deque<String> stk, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(stk));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index, i + 1);
            if (isPalindrome(str)) {
                stk.addLast(str);
                dfs(s, i + 1, stk, res);
                stk.removeLast();
            }
        }
    }

    // 第一次通过的题解
    private void dfs11(String s, StringBuilder sb, int index,
                       Deque<String> stk, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(stk));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (isPalindrome(sb.toString())) {
                stk.addLast(sb.toString());
                dfs11(s, new StringBuilder(), i + 1, stk, res);
                stk.removeLast();
            }
        }
    }

    private boolean isPalindrome(String str, int l, int r) {
        if (str == null || str.length() == 0) {
            return false;
        }
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

    private boolean isPalindrome(String str) {
        return isPalindrome(str, 0, str.length() - 1);
    }

    public static void main(String[] args) {
        Solution131 s = new Solution131();
        System.out.println(s.partition("aab"));
    }
}